package com.leet.code.lcof;

public class Code47 {

    public static void main(String[] args) {
        int[][] iii = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        int[][] ii = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };

        System.out.println(new Code47().maxValue(iii));

    }

    public int maxValue(int[][] grid) {
        return dfs(grid, 0, 0);
    }

    public int dfs(int[][] grid, int i, int j) {
        if (grid[i][j] < 0) {
            return -grid[i][j];
        }
        int iSum = 0;
        int jSum = 0;
        if (i < grid.length - 1) {
            iSum = dfs(grid, i + 1, j);
        }
        if (j < grid[0].length - 1) {
            jSum = dfs(grid, i, j + 1);
        }

        int sum = grid[i][j] + Math.max(iSum, jSum);
        grid[i][j] = -sum;
        return sum;
    }

}
